from collections import deque

import networkx as nx
import pandas as pd


def assign_device_levels(file_path):
    """
    基于物理链路配置给设备分级，将环内设备标记为-1级别

    参数:
    file_path: CSV文件路径

    返回:
    设备级别DataFrame
    """
    # 读取数据
    df = pd.read_csv(file_path, usecols=["A端设备", "Z端设备", "是否合格"], dtype=str)
    df = df[df['是否合格'] == '合格']
    df = df.dropna(subset=['A端设备', 'Z端设备'])
    df = df.drop_duplicates()

    # 创建有向图
    G = nx.DiGraph()

    # 添加边
    for _, row in df.iterrows():
        G.add_edge(row['Z端设备'], row['A端设备'])

    # 找出所有节点
    all_devices = set(G.nodes())

    # 为每个设备分配级别
    device_levels = {}

    # 找出所有入度为0的节点（最高级别设备）
    root_devices = [node for node, degree in G.in_degree() if degree == 0]

    # 如果没有入度为0的节点，需要特殊处理
    if not root_devices:
        print("警告：数据中没有入度为0的设备，所有设备可能形成环")
        print("将所有设备标记为-1级别")

        # 将所有设备标记为-1级别
        for device in all_devices:
            device_levels[device] = -1

        # 创建结果DataFrame
        result_df = pd.DataFrame({
            '设备': list(device_levels.keys()),
            '级别': list(device_levels.values())
        })

        return result_df

    # 为根节点分配级别0
    for device in root_devices:
        device_levels[device] = 0

    # 使用BFS为其他设备分配级别
    queue = deque(root_devices)

    while queue:
        current = queue.popleft()
        current_level = device_levels[current]

        for neighbor in G.successors(current):
            # 如果邻居的级别尚未分配，为其分配级别
            if neighbor not in device_levels:
                device_levels[neighbor] = current_level + 1
                queue.append(neighbor)

    # 找出所有未分配级别的设备（可能在环中）
    unassigned_devices = [device for device in all_devices if device not in device_levels]

    # 将未分配级别的设备标记为-1级别
    for device in unassigned_devices:
        device_levels[device] = -1

    # 创建结果DataFrame
    result_df = pd.DataFrame({
        '设备': list(device_levels.keys()),
        '级别': list(device_levels.values())
    })

    # 按级别排序
    result_df = result_df.sort_values(by='级别')

    return result_df


# 使用示例
if __name__ == "__main__":
    file_path = r"D:\temp\物理链路的配置查询结果.csv"
    device_levels_df = assign_device_levels(file_path)

    # 输出到CSV
    output_path = r"D:\temp\设备级别.csv"
    device_levels_df.to_csv(output_path, index=False, encoding='utf-8')

    print(f"设备级别已保存到: {output_path}")
    print("级别说明:")
    print("0: 入度为0的设备（根节点）")
    print("-1: 环内设备或无法从根节点到达的设备")
    print("其他正整数: 表示相对于根节点的层级")
